package _算法思维系列._贪心算法之区间问题;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @Author: 吕庆龙
 * @Date: 2020/4/15 20:54
 * <p>
 * 功能描述:
 */
public class Summary_0056 {

    public static void main(String[] args) {
        int[][] intervals = new int[][]{{1,3},{2,6},{8,10},{15,18}};
        Summary_0056 test = new Summary_0056();
        test.merge(intervals);

    }

    /**
     * 输入: [[1,3],[2,6],[8,10],[15,18]]
     * 输出: [[1,6],[8,10],[15,18]]
     * 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
     */
    public int[][] merge(int[][] intervals) {

        if (intervals.length == 0)
            return new int[0][0];
        List<int[]> res = new ArrayList<>();

        //[start,end]  根据每个区间的start,从小到大排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        res.add(intervals[0]);

        for (int i = 1; i < intervals.length; i++) {
            //res 中最后一个元素的引用
            int[] last = res.get(res.size() - 1);
            int[] cur = intervals[i];

            if (last[1] >= cur[0]) {
                // 找到最大的 end,同时会更新res里面的数据
                last[1] = Math.max(last[1], cur[1]);
            } else {
                res.add(cur);
            }
        }

        return res.toArray(new int[0][]);
    }

}
